package leetcode.editor.cn.q1_300.q50;

import leetcode.editor.cn.util.tree.btree.BTreeUtil;
import leetcode.editor.cn.util.tree.btree.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 中序遍历判断大小就 ok
 *
 * @author qidi
 * @date 2021-12-31 15:09:53
 */
class Q0098_ValidateBinarySearchTree {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean isValidBST(TreeNode root) {
            Integer cur = null;

            Deque<TreeNode> stack = new ArrayDeque<>();
            while (root != null || !stack.isEmpty()) {
                if (root != null) {
                    stack.push(root);
                    root = root.left;
                } else {
                    root = stack.pop();
                    if (cur == null) {
                        cur = root.val;
                    } else {
                        if (cur >= root.val) {
                            return false;
                        } else {
                            cur = root.val;
                        }
                    }
                    root = root.right;
                }
            }

            return true;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0098_ValidateBinarySearchTree().new Solution();
        System.out.println(solution.isValidBST(BTreeUtil.getInstance().generateFromArray(2, 1, 4, null, null, 3, 6)));
    }
}